package com.zhangxiaofanfan.hotcode.second;

/**
 * <a href="https://leetcode.cn/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked">64. 最小路径和</a>
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode092 {
    public static void main(String[] args) {
        HotCode092 hotCode = new HotCode092();
        int[][] grid = new int[][] {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(hotCode.minPathSum(grid));
    }

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length < 1) {
            throw new RuntimeException("入参矩阵不满足要求, 请重新输入矩阵");
        }
        int row = grid.length, col = grid[0].length, rowIndex, colIndex;
        for (rowIndex = 0; rowIndex < row; rowIndex++) {
            for (colIndex = 0; colIndex < col; colIndex++) {
                if (rowIndex == 0 && colIndex == 0) {
                    continue;
                }
                grid[rowIndex][colIndex] = grid[rowIndex][colIndex] + Math.min(((rowIndex - 1 >= 0) ? grid[rowIndex - 1][colIndex] : Integer.MAX_VALUE), ((colIndex - 1) >= 0 ? grid[rowIndex][colIndex - 1] : Integer.MAX_VALUE));
            }
        }
        return grid[row - 1][col - 1];
    }
}